Browsing by Author "Mavronicolas, Marios"

Now showing items 1-20 of 111

    • Book Chapter  

      Algorithmic Game Theory and Applications 

      Mavronicolas, Marios; Lesta, Vicky Papadopoulou; Spirakis, Paul G. (John Wiley & Sons, Inc., 2007)
      Methods from game theory and mechanism design have been proven to be a powerful mathematical tool in order to understand, control, and efficiently design dynamic, complex networks, such as the Internet. Game theory provides ...
    • Article  

      Approximate Equilibria and Ball Fusion 

      Koutsoupias, Elias; Mavronicolas, Marios; Spirakis, Paul G. (2003)
      We consider selfish routing over a network consisting of m parallel links through which n selfish users route their traffic trying to minimize their own expected latency. We study the class of mixed strategies in which the ...
    • Article  

      Balancing networks: State of the art 

      Mavronicolas, Marios (1997)
      Balancing networks have recently been proposed by Aspnes et al. (Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 1991, pp. 348-358 as a new class of distributed, low-contention data structures ...
    • Conference Object  

      A catalog of ∃ℝ-complete decision problems about Nash equilibria in multi-player games 

      Bilò, Vittorio; Mavronicolas, Marios (Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016)
      [Schaefer and Štefankovic, Theory of Computing Systems, 2015] provided an explicit formulation of ∃ℝ as the class capturing the complexity of deciding the Existential Theory of the Reals, and established that deciding, ...
    • Article  

      A combinatorial characterization of properties preserved by antitokens 

      Busch, Costas; Demetriou, Neophytos; Herlihy, M.; Mavronicolas, Marios (2000)
      Balancing networks are highly distributed data structures used to solve multiprocessor synchronization problems. Typically, balancing networks are accessed by tokens, and the distribution of the tokens on the network’s ...
    • Article  

      A combinatorial treatment of balancing networks 

      Busch, Costas; Mavronicolas, Marios (1996)
      Balancing networks, originally introduced by Aspnes et al. (Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pp. 348-358, May 1991), represent a new class of distributed, low-contention data structures ...
    • Article  

      A Comparative Study of Protocols for Efficient Data Propagation in Smart Dust Networks 

      Chatzigiannakis, Ioannis; Dimitriou, Tassos D.; Mavronicolas, Marios; Nikoletseas, Sotiris E.; Spirakis, Paul G. (2004)
      Smart Dust is comprised of a vast number of ultra-small fully autonomous computing and communication devices, with very restricted energy and computing capabilities, that co-operate to accomplish a large sensing task. Smart ...
    • Article  

      A comparative study of protocols for efficient data propagation in smart dust networks 

      Chatzigiannakis, Ioannis; Dimitriou, Tassos D.; Mavronicolas, Marios; Nikoletseas, Sotiris E.; Spirakis, Paul G. (2003)
      Smart Dust is comprised of a vast number of ultra-small fully autonomous computing and communication devices, with very restricted energy and computing capabilities, that co-operate to accomplish a large sensing task. Smart ...
    • Article  

      The complexity of decision problems about nash equilibria in win-lose games 

      Bilò, Vittorio; Mavronicolas, Marios (2012)
      We revisit the complexity of deciding, given a (finite) strategic game, whether Nash equilibria with certain natural properties exist
    • Article  

      The complexity of equilibria for risk-modeling valuations 

      Mavronicolas, Marios; Monien, Burkhard (2016)
      Following the direction pioneered by Fiat and Papadimitriou in their 2010 paper [12], we study the complexity of deciding the existence of mixed equilibria for minimization games where players use valuations other than ...
    • Article  

      The complexity of pure equilibria in mix-weighted congestion games on parallel links 

      Mavronicolas, Marios; Monien, Burkhard (2015)
      We revisit the simple class of weighted congestion games on parallel links [10], where each player has a non-negative weight and her cost on the link she chooses is the sum of the weights of all players choosing the link. ...
    • Article  

      Complexity of rational and irrational Nash equilibria 

      Bilò, Vittorio; Mavronicolas, Marios (2011)
      We introduce two new decision problems, denoted as ∃ RATIONAL NASH and ∃ IRRATIONAL NASH, pertinent to the rationality and irrationality, respectively, of Nash equilibria for (finite) strategic games. These problems ask, ...
    • Article  

      Complexity of rational and irrational nash equilibria 

      Bilò, Vittorio; Mavronicolas, Marios (2014)
      We introduce two new natural decision problems, denoted as ∃ RATIONAL NASH and ∃ IRRATIONAL NASH, pertinent to the rationality and irrationality, respectively, of Nash equilibria for (finite) strategic games. These problems ...
    • Article  

      Computing Nash equilibria for scheduling on restricted parallel links 

      Gairing, M.; Lücking, T.; Mavronicolas, Marios; Monien, Burkhard (2010)
      We consider the problem of routing nusers on m parallel links under the restriction that each user may only be routed on a link from a certain set of allowed links for the user. So, this problem is equivalent to the ...
    • Conference Object  

      Computing Nash equilibria for scheduling on restricted parallel links 

      Gairing, M.; Lücking, T.; Mavronicolas, Marios; Monien, Burkhard (2004)
      We consider the problem of routing n users on m parallel links, under the restriction that each user may only be routed on a link from a certain set of allowed links for the user. Thus, the problem is equivalent to the ...
    • Article  

      Computing on a partially eponymous ring 

      Mavronicolas, Marios; Michael, Loizos; Spirakis, Paul G. (2009)
      We study the partially eponymous model of distributed computation, which simultaneously generalizes the anonymous and the eponymous models. In this model, processors have identities, which are neither necessarily all ...
    • Article  

      Computing on a partially eponymous ring 

      Mavronicolas, Marios; Michael, Loizos; Spirakis, Paul G. (2006)
      We study the partially eponymous model of distributed computation, which simultaneously generalizes the anonymous and the eponymous models. In this model, processors have identities, which are neither necessarily all ...
    • Article  

      Conditional Value-at-Risk: Structure and complexity of equilibria 

      Mavronicolas, Marios; Monien, Burkhard (2020)
      Conditional Value-at-Risk, denoted as CVaRα, is becoming the prevailing measure of risk over two paramount economic domains: the insurance domain and the financial domain
    • Article  

      Conditional value-at-risk: Structure and complexity of equilibria 

      Mavronicolas, Marios; Monien, Burkhard (2017)
      Conditional Value-at-Risk, denoted as CVaRα, is becoming the prevailing measure of risk over two paramount economic domains: the insurance domain and the financial domain
    • Article  

      Congestion games with player-specific constants 

      Mavronicolas, Marios; Milchtaich, I.; Monien, Burkhard; Tiemann, K. (2007)
      We consider a special case of weighted congestion games with player-specific latency functions where each player uses for each particular resource a fixed (non-decreasing) delay function together with a player-specific ...